# https://leetcode.cn/problems/ji-qi-ren-de-yun-dong-fan-wei-lcof/description/

from collections import deque


class Solution:
    def wardrobeFinishing(self, m: int, n: int, cnt: int) -> int:
        def digitSum(num: int) -> int:
            return sum([int(_) for _ in str(num)])

        pt = deque([(0, 0)])
        ptSet = {(0, 0)}
        res = 0
        while pt:
            # 访问
            x, y = pt.popleft()
            if digitSum(x) + digitSum(y) <= cnt:
                print(x, y)
                res += 1
                # 加节点
                if x + 1 < m and (x + 1, y) not in ptSet:
                    pt.append((x + 1, y))
                    ptSet.add((x + 1, y))
                if y + 1 < n and (x, y + 1) not in ptSet:
                    pt.append((x, y + 1))
                    ptSet.add((x, y + 1))
        return res
